perm filename PRLISP.JP[UP,DOC] blob
sn#611712 filedate 1981-09-08 generic text, type C, neo UTF8
COMMENT ā VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 Sail Prlisp Version 2.0 User's Guide
C00009 00003 (1. Introduction cont'd)
C00014 00004 3. Condition Patterns.
C00019 00005 (3. Action patterns cont'd)
C00023 00006 5. A Summary of Prlisp Primitives.
C00029 00007 (5.2 Production rule primitives cont'd)
C00035 00008 5.5 Input - Output.
C00039 00009 :::How to use PRLISP at Sail
C00044 00010 Appendix A: Some PRLISP programs
C00058 ENDMK
Cā;
Sail Prlisp Version 2.0 User's Guide
------------------------------------
The following file documents PRLISP, a production rule interpreter written
in MACLSP at MIT-AI by J.T. Galkowski. If you have any comments, gripes,
questions etc. please refer them to JP%SAIL.
This document provides a brief summary of Prlisp features, primitives, and
protocol. More can be learned by examining and running Prlisp samples such
as the ones in the Appendix. Prlisp's control structure is based on D. A.
Waterman's production system architecture as documented in Artificial
Intelligence 1 (1970), 121-170. Several modifications, such as the
elimination of "backward form" and "forward form" rules, allowing
condition pattern elements to be arbitrary LISP predicates, allowing
action pattern elements to be arbitrary LISP functions and, of course,
alterations in syntax were made for efficiency, ease of implementation,
clarity, power of expression, and compatibility with the LISP environment.
Prlisp program files may have LISP and Prlisp forms freely interspersed,
allowing the user to choose which language is most suited to the needs of
a particular routine. The Prlisp top-level must still be used to call
non-Prlisp routines.
1. Control Structure.
---------------------
1.1 Production Rules.
A production rule has two parts, a condition part and an action part. Each
part is denoted by a pattern of elements.
1.2 Production Rule Organization and Activation.
Production rules are stored in an ordered list or table (like the PDM or
Production Rule LTM of the CMU PSG system). In Prlisp, rules are indexed
by non-negative integers with rule 0 located at the top of the table and
successive table entries numbered with successively larger integers. [The
Prlisp variable "<NPRS>" is bound to the current number of entries
occupied in the table. Hence the last or bottom rule in the table is rule
number <NPRS> - 1 or, in LISP, (RULE (1- <NPRS>)).] Rules may be given an
arbitrary number of symbolic names with the DESIGNATE-RULE primitive, but
a symbolic name can only designate one particular rule. Rule indeces may
be retrieved from rule names using the RULE-LABELLED primitive. [RULE
(RULE-LABELLED 'MATCHINGRULE)) would print the rule named "MATCHINGRULE".]
CONDITION-PART and ACTION-PART extract the condition and action parts of a
rule indicated by its rule index, respectively.
Rules may be collected (by name) into non-disjoint packets (e.g., to
create a packet called "FOO": (PACKET 'FOO '(MATCHINGRULE INPUTRULE
OUTPUTRULE PROCESSRULE)) ). These packets may be INVOKEd in the action
pattern of a production rule. Once invoked, a packet is loaded into the
Current Production Rule Memory, CPRM, replacing by overwrite and erasure
the previously invoked rule packet. (The default contents of CPRM are the
contents of the entire production rule table.)
During execution, the condition pattern of each production rule in the
CPRM is matched against the Program State Vector (see section 2), PSV,
beginning with the first and moving down to subsequent entries in the
CPRM. The first rule matching the PSV is activated, which means its action
part is executed. (Thus, Prlisp activation conflicts are resolved "PDM
order," if one does not consider details of the matching process.)
Execution of an action pattern means that each element is examined
(left-to-right) and if it is non-*, it is evaluated and the corresponding
entry in the PSV is replaced by its value. Once one rule is fired, and
the execution of its action part is finished, a new rule-scanning cycle is
begun, commencing from the top of the CPRM. If no rules are activated
(because none of their condition patterns match the current PSV),
execution terminates and control exits the program.
(1. Introduction cont'd)
Because an action pattern element can be an arbitrary LISP function,
control within such an element follows the usual LISP convention. When the
function returns a value, the Prlisp control convention resumes. LISP
control convention is also followed during the evaluation of predicates
present in the condition patterns of rules. The admissibility of
arbitrary predicates in the condition pattern of a rule makes the "PDM
order" labelling of Prlisp's conflict resolution strategy somewhat
improper. Since a predicate may refer to elements in the PSV other than
the element corresponding to it in the condition pattern, a kind of "PSV
order" conflict resolution is possible in individual cases.
2. The Program State Vector (PSV).
----------------------------------
2.1 Composition.
The Program State Vector, or PSV, is a vector of all program variables.
Because Prlisp resides in a LISP environment, global LISP variables -may-
be defined (via a SETQ) and accessed within predicates or functions. This
practise is not recommended. A number of primitives have been provided
which make exercise of this capability unnecessary. From the Prlisp
standpoint, it is merely bad programming practise. (No effort was made to
exclude the capability because it soon wreaks its own kind of havoc upon
its users.)
2.2 Access.
PSV slots (a "slot" is an entry of the PSV) may be given arbitrary
symbolic labels using the SUBVECTOR-LABELLED primitive and their values
may be retrieved using the REF primitive. The PSV slot value
corresponding to a particular condition or other pattern is bound to the
token @ and @ may be used in a pattern element instead of a REF to access
the value of the PSV slot corresponding to the immediate element.
2.3 Initialization.
PSV initialization and dynamic redimensioning is accomplished using the
SUBVECTOR primitive. Redimensioning the PSV to be a smaller size results
in the loss of PSV elements on the right. Condition patterns in
production rule match only over the shorter of the lengths of the PSV of
condition pattern. The rest of the PSV slots, if the condition pattern is
shorter, or the pattern elements, if the PSV is shorter, are ignored.
Typically, SUBVECTOR is employed prior to a RUN to establish the initial
configuration and value of the PSV. Calls to SUBVECTOR within an action
pattern element have no effect on the -value- of the PSV, but only on its
size. Redefine the PSV at will: It is a useful device for keeping the PSV
size manageable in a large Prlisp program. (At any moment during
computation, usually only a very small number of all program variables are
relevant. This is due to the serial character of most digital
computation.) The computation state SAVE and RESTORE primitives are also
useful for this purpose.
3. Condition Patterns.
---------------------
Condition pattern elements may be any of the following forms:
* - indicates the slot should be ignored during matching. (The
"don't care" token.)
# - indicates the PSV slot should be an integer. (MACLISP
differentiates between relatively small integers called "fixnums"
and large integers called "bignums." # is the matching token for
fixnums. Use ### for bignums.)
## - indicates the PSV slot should be a real number. (MACLISP
conventions require that real numbers or "flonums" be written with
at least one digit to the right of the decimal, if only a zero, as
in 1.0 indicating the real number one.)
### - indicates the PSV slot should be a MACLISP bignum (a very
large integer).
%ATOM - indicates the PSV slot should be a symbolic name (an
atomic symbol).
%LIST - indicates the PSV slot should be a regular list.
An element of the fom "(EV <predicate>)" indicates "<predicate>"
should be evaluated as a LISP predicate to ascertain if the
current condition element matches the corresponding element of the
PSV. "<predicate>" may (and usually does) refer to @, which is
bound to the PSV slot value corresponding to the pattern element.
Any other symbol or list expression is taken literally and
compared with the PSV slot value corresponding to the pattern
element and, if they are EQUAL, it is regarded as a match.
3. Action Patterns.
Action patterns may contain the following elements:
* indicating that the corresponding slot of the PSV should not be
changed.
A number or symbolic atom indicating the corresponding slot of the
PSV should be changed to this value.
A list expression preceded by a single quote (otherwise known as
an apostrophe) ' indicating the corresponding slot of the PSV
should be changed to that expression.
Unquoted (those not immediately preceded by ') list expressions
are evaluated as LISP function forms, and the corresponding slot
of the PSV is changed to the value they return. LISP functions
used in this manner may refer to @ which, as in condition
patterns, is bound to the value of the corresponding slot of the
PSV. Prlisp primitives may be called from within LISP function
forms. The Prlisp primitives RESTORE and FILERESTORE have a global
effect on the value of the PSV, irrespective of whether they are
called immediately, that is, when they ARE the action pattern
element, or whether they are called from within a LISP expression
which is the action pattern element.
(3. Action patterns cont'd)
An unquoted list expression of the form (EV '<symbol>) means that
the corresponding slot of the PSV should be changed to the value
of the variable "<symbol>". (This feature implements indirect
referencing of values.)
An unquoted list expression of the form (EV <expression>) means
that the corresponding slot of the PSV should be changed to the
value of the variable name - which must be an atomic symbol -
returned by an evaluation of the LISP expression "<expression>".
A list of the form:
( <Prlisp primitive> <arg 1> . . . <arg n> )
means that the Prlisp primitive "<Prlisp primitive>" should be
called with the specified arguments. Note that the only legal
non-local change to the PSV is effected by calling either RESTORE
or FILERESTORE.
4. Classes.
-----------
Prlisp contains two primitives which create and test membership in classes
of data objects. DEFCLASS defines a class and CLASS queries whether an
object is a member of a particular class. Certain "system classes" are
predefined in Prlisp and may be useful. They are listed below. For the
most part, the class definitions are self-evident.
CLASSES NUMBERS SYMBOLS ALPHABET
DIGITS INTEGERS REALS POSITIVE-INTEGERS
NON-NEGATIVE-INTEGERS NON-NEGATIVE-REALS
POSITIVE-REALS NEGATIVE-REALS
Prlisp-PRIMITIVES NAMED-RULES PACKETS
ACTIVE-COMPUTATION-STATES
Three classes, INTEGERS, REALS, and Prlisp-PRIMITIVES need not be quoted
in a CLASS call. They should not be SETQ'd from LISP since this will
destroy the reference to the class name. CLASSES is automatically
augmented when a DEFCLASS is performed.
DEFCLASS is called by (DEFCLASS <classname> <predicate>), where
"<classname>" must evaluate to an atomic symbol, and "<predicate>" is the
defining predicate for the class of objects. "<predicate>" must explicitly
refer to the atomic symbol "<OBJECT>", the candidate for the class
membership test.
CLASS is called by (CLASS <thing> <classname>), where "<thing>" evaluates
to the object whose class membership is to be tested, and "<classname>"
evaluates to the name of a class, which must be an atomic symbol.
5. A Summary of Prlisp Primitives.
----------------------------------
[In the following descriptions and unless otherwise indicated, expressions
represented as "<....>" are evaluated in the LISP sense and must be
QUOTEd (') if they are to represent literals. Numbers and special symbolic
constants (that is, T, NIL, INTEGERS, REALS, Prlisp-PRIMITIVES, \, and \\)
evaluate to themselves and hence, need not be quoted.]
5.1 PSV Primitives.
(SUBVECTOR <list>)
defines the PSV as a vector of (LENGTH <list>) and fills it with
consecutive elements from <list>. A SUBVECTOR statement generally
precedes a call to (RUN) in a Prlisp source program. Otherwise the PSV
defaults to a vector of length seven, filled with NILs. SUBVECTOR may
also be used to dynamically redefine the size of the PSV. In that
case, only the LENGTH of the <list> is of any significance.
(LABEL-SUBVECTOR <atomlist>)
where <atomlist> evaluates to a list of atomic symbols, labels the kth
slot of the PSV with the kth element of <atomlist>.
(REF <label>)
returns the value of the PSV slot labelled by <label>. If <label> is
not a proper PSV slot label, then an error is signalled.
(SLOT-LABELLED <label>)
returns the index of the PSV slot labelled by <label>. If <label> is
not a proper PSV slot label, then an error is signalled.
5.2 Production Rule Primitives.
(PR <condition pattern> <action pattern>)
inserts the rule:
<condition> ---> <action>
at the bottom of the Production Rule table. (NOTE: Not the CPRM !!)
(PRR <condition pattern> <action pattern>)
inserts a rule like PR, except the rule is positioned at the top of
the Production Rule table and the other rules are moved down one
position in the table. Rule positions (i.e., entry numbers) are not
invariant across a PRR, but in the current version, rule designations
or names ARE invariant across a PRR.
(SR <rule index> <condition pattern> <action pattern>)
Sets the position indicated by <rule index> (which must evaluate to a
non-negative integer) to the specified new rule. Only table positions
which contain or formerly contained rules are SRable.
(RULE <rule index>)
displays the condition and action parts of the rule at <rule index>.
Used principally for debugging.
(ERASE-RULE <rule index>)
erases the specified rule. The other rules in the production rule
table are unaffected.
(SWAP-RULES <rule index 1> <rule index 2>)
swaps the specified rules in the Production Rule table. Note that
numbers referring to those rules may no longer be correct after a
swap, but their designations must be.
(DESIGNATE-RULE <rule index> <name>)
gives the specified rule the name <name>. "<name>" must evaluate to an
atomic symbol.
(RULE-NAMED <name>)
returns the rule index of the rule named <name>. <name> must evaluate
to a proper rule name or an error is signalled.
(CONDITION-PART <rule index>)
returns the condition pattern of rule <rule index>.
(ACTION-PART <rule index>)
returns the action pattern of rule <rule index>.
(ENSYST <rule index> <packet name>)
makes rule <rule index> part of rule packet <packet name>, where
<packet name> must evaluate to an atomic symbol. If "(ENSYST 2. 'A)
(ENSYST 1. 'A)" are done, then the packet called "A" will have rules 2
and 1 in it, in that order.
(5.2 Production rule primitives cont'd)
(PACKET <packet name> <rule name list>)
creates packet <packet name> with rules whose names are on the list
<rule name list>. Note that this implies rules which are collected in
packets must be named via "DESIGNATE-RULE" prior to their use in a
packet definition. If <packet name> exists prior to a PACKET, then
the rules in <rule name list> are appended to its end.
(INVOKE <packet name>)
replaces the current contents of the CPRM with the rules in <packet
name>. Execution commences on the next cycle with those rules rather
than current packet rules.
5.3 Classes.
(DEFCLASS <name> <predicate>)
defines a class of name <name>. <predicate> must define the class in
terms of the global variable "<OBJECT>": If <OBJECT> is a member of
the class, then <predicate> should return T; NIL otherwise.
(CLASS <thing> <name>)
returns T if <thing> is a member of class <name>; NIL otherwise.
<name> must evaluate to a literal classname else an error will be
signalled. CLASS's principal mode of use is in the condition pattern
of a production rule as (EV (CLASS @ <classname>)) which checks to see
that the corresponding PSV slot value is a member of class
<classname>.
5.4 Environments and Environment Manipulation.
(SAVE)
saves a copy of the current execution environment and returns a tag
pointing to that environment. At a later time, the environment may be
restored by calling RESTORE with the tag as its argument. Except for
possibly dumping of the returned tag into a PSV slot, and augmenting
the ACTIVE-COMPUTATION-STATES class, SAVE leaves the current execution
environment unaltered.
(RESTORE <tag>)
restores the environment associated with the tag <tag> which must
evaluate to an atomic symbol. If the value that RESTORE returns is
deposited in a PSV slot, then the previous contents of that slot are
preserved across the environment restoration.
(SCRUBTAG <tag>)
disassociates any and all environments from <tag>. Since such
environments are likely to occupy a great deal of memory space,
SCRUBTAG is provided to encourage conservation. <tag> must evaluate to
an atomic symbol.
(FILESAVE <filename>)
is exactly like SAVE except that the environment is deposited in a
disk file denoted by a MACLSP UREAD I/O 4-tuple <filename> in the form
"( <filename1> <filename2> DSK (proj prog))", instead of being
retained in primary memory. FILESAVE returns a tag like SAVE but the
tag must be used in a FILERESTORE, not a regular RESTORE.
(FILERESTORE <source>)
is exactly like RESTORE except it retrieves the environment from a
disk file denoted by <source>. <source> is either a FILESAVE tag or a
LISP UREAD file 4-tuple indicating the file to be read to acquire the
environment.
(SCRUB-RESTORE <tag>)
behaves like a RESTORE except the environment restored is
disassociated from <tag> after restoration.
5.5 Input - Output.
(ACCEPT-PROMPT <expression>)
will display <expression> then accept and return a LISP item as its
value.
(WRITE <expression>)
is like the MACLISP PRINT, but suppresses slashes on slashified
characters like the MACLISP PRINC. If <expression> is EQ "\", a LISP
TERPRI (carriage-return, line-feed) is done.
(OUTTEXT <expression>)
begins a record of all output material on the current LISP
device-directory headed by <expression>, unless <expression> is EQ
"\\". If <expression> IS EQ "\\" then all the output collected since
the last OUTTEXT is recorded on the file named "TXTOUT.PRL" on the
current device-directory. Note that until Prlisp I/O is recoded using
the NEWIO facility of MACLISP (and that should not happen until NEWIO
stabilizes), one cannot properly OUTTEXT if FILESAVEs are being done.
5.6 Miscellaneous.
The global variable ELSE is synonomous with the special constant T. This
allows the last clause of a LISP COND to be written (ELSE ...).
(CALL <expression> <name>)
sets the atomic symbol <name> as the name of the arbitrary expression
<expression>. <name> must evaulate to an atomic symbol.
(ATOMIC <name>)
declares <name> to be an atomic symbol representing itself. (Thus,
ATOMIC is a function for generating special LISP constants like T,
NIL, REALS, etc.) After such a call, <name> need no longer be quoted
when used in an expression. Clearly, <name> must evaluate to an
atomic symbol.
(TRACE-ON)
enables tracing of an executing Prlisp program.
(TRACE-OFF)
disables tracing of an executing Prlisp program.
(PRECESS)
invokes a syntax preprocessor which converts a Prlisp source file
using the syntax convention,
"( <condition> --> <action> )"
instead of explicit calls to PR, to a file acceptable to (Prlisp)
using PR forms. Invoke (PRECESS) and follow directions. Output is
sent to PRECES.OUT on the current device-directory. PRECES OUTPUT may
then be loaded into Prlisp and executed.
:::How to use PRLISP at Sail
----------------------------
Prepare your PRLISP program using one of the editors (hopefully E!). LISP
function definitions and forms may be freely interspersed with PRLISP
code. Production rules are typically defined using the PR primitive
because their position in the Production Rule table is then the same as
their order in the source file. The program source file must be ended by
placing "(EOF)" at the bottom. A "load-and-go" program can be written by
placing "(RUN)" at the bottom of the file prior to the "(EOF)". Be sure
"load-and-go" program files contain a SUBVECTOR definition, unless you are
satisfied with the Prlisp PSV default. An alternative style of source
program preparation is to define production rules using the "-->" syntax
and process them using PRECESS (q.v.).
***** notice change below!! *****
Once a PRLISP source file is prepared, get a MACLISP space (i.e. do r
MACLSP) and allocate 23000 BPS, in order to be able to load the compiled
PRLISP code. If your program requires PRECESSing do (precess) at MACLSP
top level and then do (prlisp) on the PRECESSed file, otherwise just do
(prlisp). (PRLISP) will start up the rule interpreter and prompt you for
a source file name. If you don't want any file to be read give some
atomic negative response, and you will be left at MACLSP top level. If you
give a file specifier (a 2 or 4-list) reading will proceed from that file
in the manner desribed above. Note that Prlisp currently has a
prespecified upper-limit of 400 on the number of rules. If you need more,
send mail to JP. All Prlisp filenames are specified as a 4-tuple like
"(foo bar dsk (ble tch))", for example.
Prlisp programs which do not have "(RUN)" in them (that is, that are not
"load-and-go" programs) may be executed after Prlisp displays "-EOF-" by
typing "(RUN)". "(TRACE-ON)", "(TRACE-OFF)", and the OUTTEXT command may
be used before RUN.
Bugs? Yea, bugs!
----------------
Most bugs in your Prlisp program will be indicated by a ";BKPT Prlisp".
Other problems may be due (especially) to trying to use a symbolic atom as
a number or a number of the wrong type in the wrong place and these may be
indicated by LISP error messages rather than Prlisp error messages. In
either case, it may be possible to partially recover, either by doing a
"(TRACE-ON)" and doing "(Prlisp)" again to reload your program for a
step-by-step traced run, or by typing "ESC-P-SPACE", where "ESC" means the
"escape" character, and "SPACE" means a space (the "-" in the string is
only metalinguistic), which attempts to continue with the current run.
MACLSP provides other options for replying to such a BREAKPOINT loop,
including returning with a particular value (not much good unless you are
familiar with the interpreter), or SETQing a variable, then doing the
continuation "ESC-P-SPACE" command, hoping that the altered variable may
be the source of the problem.
Appendix A: Some PRLISP programs
The following are some sample programs that you can use to familiarize
yourself with the rule interpreter.
Example 1: Computing Factorial
;;; Prlisp: Example 1. Computing the fctorial function
(SUBVECTOR '(NIL NIL))
(LABEL-SUBVECTOR '(N F))
(PR '((EV (NOT (FIXP @))) *)
'((PROG2 (TERPRI) (PROG2 (PRINC 'N=) (READ))) 1.))
(PR '((EV (< @ 2.)) *)
'(NIL (PROG2 (TERPRI) (PRINT (LIST 'FACTORIAL= @)))))
(PR '(* *) '((1- @) (* (REF 'N) @)))
(TRACE-ON)
(RUN)
Example 2: A simple classification program
;;; Prlisp Example 2: CLASS
(SUBVECTOR '(T T))
(LABEL-SUBVECTOR '(SET SET-ELEMENT))
(PR '((EV (NULL @)) *)
'((PRINT '(DOESNT FIT)) *))
(PR '((EV (NOT (EQ (TYPEP @) 'LIST))) *)
'((PROG2 (PRINC '|Input set=|) (READ))
(PROG2 (PRINC '|Element =|) (READ))))
(PR '(* (EV (EQUAL (CAR (REF 'SET)) @)))
'((PRINT '(FITS)) *))
(PR '(* *) '((CDR @) *))
(RUN)
Example 3: The Tower of Hanoi problem
; Example 3. The tower of Hanoi problem. Demonstrates recursion in production rule
; system.
(LABEL-SUBVECTOR '(N NS ND NI STASH MODE))
(PR '(* * * * NIL POP)
'((WRITE 'PUZZLE/ DONE/ ) * * * * END)) ; RULE 0
(PR '((EV (NOT (FIXP @))) * * * * ENTER1)
'((ACCEPT-PROMPT '#/ DISCS/ NOT/ NUMERIC/././.RE-ENTER:/ )
*
*
*
*
*)) ; RULE 1
(PR '(* * * * * POP)
'((CAAR (REF 'STASH))
(CADR (CAR (REF 'STASH)))
(CADDR (CAR (REF 'STASH)))
(CADDR (CDAR (REF 'STASH)))
(CDR @)
(CADR (CDDR (CDAR (REF 'STASH)))))) ; RULE 2
(PR '(0. * * * * *) '(* * * * * POP)) ; RULE 3
(PR '(* * * * * ENTER1)
'((1- @)
*
(REF 'NI)
(REF 'ND)
(CONS (LIST (REF 'N)
(REF 'NS)
(REF 'ND)
(REF 'NI)
'PRINT)
@)
*)) ; RULE 4
(PR '(* * * * * PRINT)
'(* *
*
*
*
(PROG2 (PRINT (LIST 'MOVE
'DISC
(REF 'N)
'FROM
'PEG
(REF 'NS)
'TO
'PEG
(REF 'ND)))
'ENTER2))) ; RULE 5
(PR '(* * * * * ENTER2)
'((1- @)
(REF 'NI)
(REF 'ND)
(REF 'NS)
(CONS (LIST (REF 'N)
(REF 'NS)
(REF 'ND)
(REF 'NI)
'POP)
@)
ENTER1)) ; RULE 6
(DEFUN # (X) (1- X)) ; UTILITY FOR MAKING DESIGNATIONS
;READABLE
(DESIGNATE-RULE (# 1.) 'DONERULE)
(DESIGNATE-RULE (# 2.) 'POPRULE)
(DESIGNATE-RULE (# 3.) 'EMPTYPEGRULE)
(DESIGNATE-RULE (# 4.) 'S-DISC-I-RULE)
(DESIGNATE-RULE (# 5.) 'STEPDISPLAYRULE)
(DESIGNATE-RULE (# 6.) 'I-DISC-D-RULE)
(PROG2
(EOF)
(PROG2
(SUBVECTOR
(LIST (ACCEPT-PROMPT 'NUMBER/ OF/ DISCS/ ON/ STARTING/ PEG:/ )
(PROG2 (PRINT '(STARTING PEG NAME)) (READ))
(PROG2 (PRINT '(DESTINATION PEG NAME)) (READ))
(PROG2 (PRINT '(OTHER PEG NAME)) (READ))
NIL
'ENTER1))
(RUN)))